class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(int i = 0;  i < stones.size(); i++)
        {
            sum += stones[i];
        }
        int target = sum/2;
        vector<int> dp(target + 1,0);
        for(int i = 0; i < stones.size();i++)
        {
            for(int j = target;j >= stones[i];j--)
            {
                dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]);
            }
        }
        //dp数组求出来的dp[target]是最大能背的石头
        //其实和切割等子集是一样的,也是找到最多能相等的，剩下的一半里面就肯定是相等的或者有多出来的所以说就返回这个值
        return sum - dp[target] - dp[target];
    }
};